package DoExercise.HSP_ZCY.A016_动态规划;

/**
 * 假设有排成一行的N个位置，记为1~N，N 一定大于或等于 2
 * 开始时机器人在其中的M位置上(M 一定是 1~N 中的一个)
 * 如果机器人来到1位置，那么下一步只能往右来到2位置；
 * 如果机器人来到N位置，那么下一步只能往左来到 N-1 位置；
 * 如果机器人来到中间位置，那么下一步可以往左走或者往右走；
 * 规定机器人必须走 K 步，最终能来到P位置(P也是1~N中的一个)的方法有多少种
 * 给定四个参数
 * N ：位置
 * M：初始位置
 * K：一定要走的步骤
 * P：目标位置
 * <p>
 * 返回方法数。
 * <p>
 * 1 2 3 4 5 6 7
 * <p>
 * 3-2-3-2  方法1
 * 3-2-1-2  方法2
 * <p>
 * N = 7
 * M = 3
 * P = 2
 * K = 3
 */
public class Code01_机器人运动问题
{
    public static void main(String[] args)
    {
        System.out.println(ways1(7, 4, 9, 5));
        System.out.println(ways2( 7, 4, 9, 5));
        System.out.println(ways3(7, 4, 9, 5));
        System.out.println(ways4(7, 4, 9, 5));
        System.out.println(ways5(7, 4, 9, 5));
    }
    
    public static int ways1(int N, int M, int K, int P)
    {
        // 参数无效直接返回0
        if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N)
        {
            return 0;
        }
        // 总共N个
        // 位置，从M点出发，还剩K步，返回最终能达到P的方法数
        return process(N, M, K, P);
    }
    
    /**
     * 该函数的含义：只能在1~N这些位置上移动，当前在cur位置，走完rest步之后，停在P位置的方法数作为返回值返回
     *
     * @param N    位置为1 ~ N，固定参数
     * @param cur  当前在cur位置，可变参数
     * @param rest 还剩res步没有走，可变参数
     * @param P    最终目标位置是P，固定参数
     * @return
     */
    public static int process(int N, int cur, int rest, int P)
    {
        /**
         * 如果没有剩余步数了，当前的cur位置就是最后的位置
         * 如果最后的位置停在P上，那么之前做的移动是有效的；如果最后的位置没在P上，那么之前做的移动是无效的
         */
        if (rest == 0)
        {
            return cur == P ? 1 : 0;//不能用cur == P 做条件，因为p是固定参数
        }
        if (cur == 1)//只能往右走
        {
            return process(N, 2, rest - 1, P);
        }
        if (cur == N)//只能相左走
        {
            return process(N, N - 1, rest - 1, P);
        }
        //向左走和向右走的和
        return process(N, cur + 1, rest - 1, P) + process(N, cur - 1, rest - 1, P);
    }
    
    /**
     * 动态规划一定是由暴力递归抽象而来，但是暴力递归不一定都能抽象为动态规划
     * 动态规划的图
     *
     * @param N
     * @param M
     * @param K
     * @param P
     * @return
     */
    public static int ways2(int N, int M, int K, int P)
    {
        // 参数无效直接返回0
        if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N)
        {
            return 0;
        }
        int[][] dp = new int[K + 1][N + 1];
        dp[0][P] = 1;
        for (int i = 1; i <= K; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                if (j == 1)
                {
                    dp[i][j] = dp[i - 1][2];
                } else if (j == N)
                {
                    dp[i][j] = dp[i - 1][N - 1];
                } else
                {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
                }
            }
        }
        return dp[K][M];
    }
    
    public static int ways3(int N, int M, int K, int P)
    {
        // 参数无效直接返回0
        if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N)
        {
            return 0;
        }
        int[] dp = new int[N + 1];
        dp[P] = 1;
        for (int i = 1; i <= K; i++)
        {
            int leftUp = dp[1];// 左上角的值
            for (int j = 1; j <= N; j++)
            {
                int tmp = dp[j];
                if (j == 1)
                {
                    dp[j] = dp[j + 1];
                } else if (j == N)
                {
                    dp[j] = leftUp;
                } else
                {
                    dp[j] = leftUp + dp[j + 1];
                }
                leftUp = tmp;
            }
        }
        return dp[M];
    }
    
    // ways4是你的方法
    public static int ways4(int N, int M, int K, int P)
    {
        if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N)
        {
            return 0;
        }
        return process(N, 0, P, M, K);
    }
    
    // 一共N个位置，从M点出发，一共只有K步。返回走到位置j，剩余步数为i的方法数
    public static int process(int N, int i, int j, int M, int K)
    {
        if (i == K)
        {
            return j == M ? 1 : 0;
        }
        if (j == 1)
        {
            return process(N, i + 1, j + 1, M, K);
        }
        if (j == N)
        {
            return process(N, i + 1, j - 1, M, K);
        }
        return process(N, i + 1, j + 1, M, K) + process(N, i + 1, j - 1, M, K);
    }
    
    // ways5是你的方法的dp优化
    public static int ways5(int N, int M, int K, int P)
    {
        if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N)
        {
            return 0;
        }
        int[][] dp = new int[K + 1][N + 1];
        dp[K][M] = 1;
        for (int i = K - 1; i >= 0; i--)
        {
            for (int j = 1; j <= N; j++)
            {
                if (j == 1)
                {
                    dp[i][j] = dp[i + 1][j + 1];
                } else if (j == N)
                {
                    dp[i][j] = dp[i + 1][j - 1];
                } else
                {
                    dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j - 1];
                }
            }
        }
        return dp[0][P];
    }
    
    
}
